<html>
<head><meta charset="utf-8"><title>APIs for BTree · t-libs · Zulip Chat Archive</title></head>
<h2>Stream: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/index.html">t-libs</a></h2>
<h3>Topic: <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html">APIs for BTree</a></h3>

<hr>

<base href="https://rust-lang.zulipchat.com">

<head><link href="https://rust-lang.github.io/zulip_archive/style.css" rel="stylesheet"></head>

<a name="221076386"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221076386" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> garro <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221076386">(Dec 28 2020 at 17:29)</a>:</h4>
<p>Hi all, I was thinking about some APIs for getting the predecessor, successor or closest value from a BTreeMap or BTreeSet given a key. I think these methods would fit into a tree-like data structure and could be implemented with reasonable complexity. I would like to collect some opinions about this. Thanks</p>



<a name="221076557"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221076557" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> garro <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221076557">(Dec 28 2020 at 17:31)</a>:</h4>
<p>A use case of this API could be  the implementation of an Interval Tree</p>



<a name="221077500"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221077500" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> simulacrum <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221077500">(Dec 28 2020 at 17:44)</a>:</h4>
<p>I'm pretty sure the design is being pioneered with cursors on linked list, first, and then once we feel good there expect to extend it to btree.</p>



<a name="221082624"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221082624" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> garro <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221082624">(Dec 28 2020 at 18:52)</a>:</h4>
<p>But I think a simpler API could be implemented also without cursors: what I am thinking to could look like</p>
<div class="codehilite"><pre><span></span><code>predecessor(key: &amp;Q) -&gt; (&amp;K, &amp;V)
successor(key: &amp;Q) -&gt; (&amp;K, &amp;V)
...
</code></pre></div>



<a name="221116312"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221116312" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> scottmcm <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221116312">(Dec 29 2020 at 07:05)</a>:</h4>
<p><code>.predecessor(k)</code> is <code>.range(..k).next_back()</code>, FWIW, and there's a similar <code>RangeBounds</code> approach for successor too.</p>
<p>(Note that you're missing some <code>Option&lt;_&gt;</code> in those signatures.)</p>



<a name="221120512"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221120512" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> garro <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221120512">(Dec 29 2020 at 08:53)</a>:</h4>
<p>Yeah, sorry for missing <code>Option</code>s.<br>
Probably <code>.predecessor(k)</code> would be more explicit then <code>.range(..k).next_back()</code> though. <br>
On the other hand, also <code>first</code> and <code>last</code> in slices could be obtained through other methods with the same complexity and results (<code>get(0)</code> and <code>x.get(x.len())</code>), although it was chosen to implement the more explicit methods.<br>
And I am not even sure that <code>.range(..k).next_back()</code> has the best complexity, as I did not check the implementation.</p>



<a name="221121745"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221121745" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> garro <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221121745">(Dec 29 2020 at 09:20)</a>:</h4>
<p>For example, <code>.range</code> searches for the range start, that could be avoided if one is only interested in the predecessor of a given key, and for the end, that is not needed if only the successor is requested</p>



<a name="221277693"></a>
<h4><a href="https://rust-lang.zulipchat.com#narrow/stream/219381-t-libs/topic/APIs%20for%20BTree/near/221277693" class="zl"><img src="https://rust-lang.github.io/zulip_archive/assets/img/zulip.svg" alt="view this post on Zulip" style="width:20px;height:20px;"></a> garro <a href="https://rust-lang.github.io/zulip_archive/stream/219381-t-libs/topic/APIs.20for.20BTree.html#221277693">(Dec 31 2020 at 08:49)</a>:</h4>
<p>If I would like to go on with this proposal, what is the right way to proceed? Should I do a Pull Request or open an issue? Or should I start an RFC?</p>



<hr><p>Last updated: Aug 07 2021 at 22:04 UTC</p>
</html>